#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
回文素数查找器
=============

功能描述：
1. 判断一个数是否为素数（只能被1和自身整除的数）
2. 判断一个数是否为回文数（正着读和反着读一样，如131）
3. 找出1到1,000,000之间既是素数又是回文数的所有数字
4. 将这些「回文素数」写入文本文件，每行记录一个数字

使用方法：
- 运行测试：python palindrome_primes.py test
- 运行主程序：python palindrome_primes.py
- 如果没有Python，可以安装后运行，或者查看代码学习算法

作者：CSDN技术博客
创建时间：2024年
兼容性：Python 2.7+ 和 Python 3.x
"""

import time
import math


def is_prime(n):
    """
    判断一个数是否为素数
    
    算法说明：
    - 素数定义：只能被1和自身整除的大于1的自然数
    - 优化策略：只需检查到√n即可，因为大于√n的因子必然对应一个小于√n的因子
    
    Args:
        n: 待检查的数字
        
    Returns:
        如果是素数返回True，否则返回False
        
    Examples:
        >>> is_prime(2)
        True
        >>> is_prime(4)
        False
        >>> is_prime(17)
        True
    """
    # 处理特殊情况
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # 只检查奇数因子，从3开始到√n
    sqrt_n = int(math.sqrt(n)) + 1
    for i in range(3, sqrt_n, 2):
        if n % i == 0:
            return False
    
    return True


def is_palindrome(n):
    """
    判断一个数是否为回文数
    
    算法说明：
    - 回文数：正着读和反着读都一样的数字，如131、2332
    - 实现方式：将数字转换为字符串，比较原字符串和反转字符串
    
    Args:
        n (int): 待检查的数字
        
    Returns:
        bool: 如果是回文数返回True，否则返回False
        
    Examples:
        >>> is_palindrome(131)
        True
        >>> is_palindrome(123)
        False
        >>> is_palindrome(2332)
        True
    """
    # 将数字转换为字符串
    str_n = str(n)
    
    # 比较原字符串和反转字符串
    return str_n == str_n[::-1]


def is_palindrome_optimized(n):
    """
    判断回文数的优化版本（数学方法）
    
    算法说明：
    - 不使用字符串转换，纯数学方法
    - 通过数学运算反转数字，然后比较
    
    Args:
        n (int): 待检查的数字
        
    Returns:
        bool: 如果是回文数返回True，否则返回False
    """
    if n < 0:
        return False
    
    original = n
    reversed_num = 0
    
    # 数学方法反转数字
    while n > 0:
        reversed_num = reversed_num * 10 + n % 10
        n //= 10
    
    return original == reversed_num


def find_palindrome_primes(start=1, end=1000000):
    """
    查找指定范围内的所有回文素数
    
    算法说明：
    - 使用生成器模式，节省内存
    - 先检查回文数（更快），再检查素数
    - 对于大范围搜索，这种顺序能提高效率
    
    Args:
        start (int): 搜索起始值（默认1）
        end (int): 搜索结束值（默认1,000,000）
        
    Yields:
        int: 每个找到的回文素数
        
    Examples:
        >>> list(find_palindrome_primes(1, 100))
        [2, 3, 5, 7, 11]
    """
    print(f"🔍 开始搜索范围：{start:,} 到 {end:,}")
    
    count = 0
    for num in range(start, end + 1):
        # 先检查是否为回文数（通常更快）
        if is_palindrome(num):
            # 再检查是否为素数
            if is_prime(num):
                count += 1
                print(f"✅ 找到第 {count} 个回文素数: {num}")
                yield num


def save_to_file(palindrome_primes, filename="palindrome_primes.txt"):
    """
    将回文素数列表保存到文本文件
    
    Args:
        palindrome_primes (List[int]): 回文素数列表
        filename (str): 输出文件名（默认"palindrome_primes.txt"）
    """
    try:
        with open(filename, 'w', encoding='utf-8') as f:
            # 写入文件头信息
            f.write("# 回文素数列表\n")
            f.write(f"# 生成时间: {time.strftime('%Y-%m-%d %H:%M:%S')}\n")
            f.write(f"# 总数量: {len(palindrome_primes)}\n")
            f.write("# 格式: 每行一个数字\n")
            f.write("-" * 40 + "\n")
            
            # 写入每个回文素数
            for prime in palindrome_primes:
                f.write(f"{prime}\n")
        
        print(f"💾 成功保存 {len(palindrome_primes)} 个回文素数到文件: {filename}")
        
    except IOError as e:
        print(f"❌ 文件保存失败: {e}")


def display_statistics(palindrome_primes):
    """
    显示回文素数的统计信息
    
    Args:
        palindrome_primes (List[int]): 回文素数列表
    """
    if not palindrome_primes:
        print("📊 没有找到回文素数")
        return
    
    print("\n" + "="*50)
    print("📊 回文素数统计信息")
    print("="*50)
    print(f"总数量: {len(palindrome_primes)}")
    print(f"最小值: {min(palindrome_primes)}")
    print(f"最大值: {max(palindrome_primes)}")
    print(f"平均值: {sum(palindrome_primes) / len(palindrome_primes):.2f}")
    
    # 按位数分组统计
    digit_groups = {}
    for prime in palindrome_primes:
        digits = len(str(prime))
        digit_groups[digits] = digit_groups.get(digits, 0) + 1
    
    print("\n按位数分布:")
    for digits in sorted(digit_groups.keys()):
        print(f"  {digits}位数: {digit_groups[digits]} 个")
    
    # 显示前10个和后10个
    print(f"\n前10个: {palindrome_primes[:10]}")
    if len(palindrome_primes) > 10:
        print(f"后10个: {palindrome_primes[-10:]}")


def main():
    """
    主函数：执行完整的回文素数查找流程
    """
    print("🐍 Python回文素数查找器")
    print("=" * 50)
    
    # 记录开始时间
    start_time = time.time()
    
    # 设置搜索范围
    search_start = 1
    search_end = 1000000
    
    print(f"🎯 任务目标:")
    print(f"   ✅ 编写函数判断一个数是否为素数")
    print(f"   ✅ 编写函数判断一个数是否为回文数")
    print(f"   ✅ 找出{search_start:,}到{search_end:,}之间既是素数又是回文数的所有数字")
    print(f"   ✅ 将这些「回文素数」写入文本文件")
    print()
    
    # 查找回文素数
    palindrome_primes = list(find_palindrome_primes(search_start, search_end))
    
    # 计算耗时
    end_time = time.time()
    elapsed_time = end_time - start_time
    
    # 显示统计信息
    display_statistics(palindrome_primes)
    
    # 保存到文件
    save_to_file(palindrome_primes)
    
    # 显示性能信息
    print(f"\n⏱️  执行时间: {elapsed_time:.2f} 秒")
    print(f"🚀 平均速度: {search_end / elapsed_time:.0f} 数字/秒")
    
    print("\n🎉 任务完成！")


def test_functions():
    """
    测试函数的正确性
    """
    print("🧪 运行测试用例...")
    
    # 测试素数判断
    test_primes = [
        (2, True), (3, True), (4, False), (5, True), 
        (17, True), (25, False), (97, True), (100, False)
    ]
    
    print("测试素数判断:")
    for num, expected in test_primes:
        result = is_prime(num)
        status = "✅" if result == expected else "❌"
        print(f"  {status} is_prime({num}) = {result} (期望: {expected})")
    
    # 测试回文数判断
    test_palindromes = [
        (121, True), (131, True), (123, False), (2332, True),
        (1, True), (11, True), (12, False)
    ]
    
    print("\n测试回文数判断:")
    for num, expected in test_palindromes:
        result = is_palindrome(num)
        status = "✅" if result == expected else "❌"
        print(f"  {status} is_palindrome({num}) = {result} (期望: {expected})")
    
    print("\n🎯 测试完成！")


if __name__ == "__main__":
    # 可以选择运行测试或主程序
    import sys
    
    if len(sys.argv) > 1 and sys.argv[1] == "test":
        test_functions()
    else:
        main()